This invention relates, in general, to computer error correction codes and, in particular, to an error correction code, generated according to a novel H-matrix, for use in correcting all single symbol errors and detecting all double symbol errors in a data word.
The small size of computer transistors and capacitors, combined with transient electrical and electromagnetic phenomena cause occasional errors in stored information in computer memory systems. Therefore, even well-designed and generally reliable memory systems are susceptible to memory device failures.
In an effort to minimize the effects of these memory device failures, various error checking schemes have been developed to detect, and in some cases correct, errors in messages read from memory. The simplest error detection scheme is the parity bit. A parity bit is an extra bit included with a binary data message or data word to make the total number of 1""s in the message either odd or even. For xe2x80x9ceven parityxe2x80x9d systems, the parity bit is set to make the total number of 1""s in the message even. For xe2x80x9codd parityxe2x80x9d systems, the parity bit is set to make the total number of 1""s in the message odd. For example, in a system utilizing odd parity, a message having two 1""s would have its parity bit set to 1, thereby making the total number of 1""s odd. Then, the message including the parity bit is transmitted and subsequently checked at the receiving end for errors. An error results if the parity of the data bits in the message does not correspond to the parity bit transmitted. As a result, single bit errors can be detected. However, since there is no way to detect which particular bit is in error, correction is not possible. Furthermore, if two or any even number of bits are in error, the parity will be correct and no error will be detected. Parity therefore is capable of detecting only odd numbers of errors and is not capable of correcting any bits determined to be in error.
Error correction codes (ECCs) have thus been developed to not only detect but also correct bits determined to be in error. ECCs utilize multiple parity check bits stored with the data message in memory. Each check bit is a parity bit for a group of bits in the data message. When the message is read from memory, the parity of each group, including the check bit, is evaluated. If the parity is correct for all of the groups, it signifies that no detectable error has occurred. If one or more of the newly generated parity values are incorrect, a unique pattern called a syndrome results which may be used to identify the bit in error. Upon detection of the particular bit in error, the error may be corrected by complementing the erroneous bit.
A widely used type of ECC utilized in error control in digital systems is based on the codes devised by R. W. Hamming, and thus take the name xe2x80x9cHamming codesxe2x80x9d. One particular subclass of Hamming codes includes the single error correcting and double error detecting (SEC-DED) codes. As their name suggests, these codes may be utilized not only to correct any single bit error but also to detect double bit errors.
Another type of well-known ECC is the single symbol correction and double symbol detection (SSC-DSD) codes which are used to correct single symbol errors and detect double symbol errors. In systems implementing these types of codes, the symbol represents a multiple bit package or chip. Hence, as the name implies, an SSC-DSD code in a system utilizing n bit symbols would be capable of correcting n bits in a single symbol and detecting errors occurring in double symbols.
In any of these systems, and as with digital systems in general, ease of implementation is always desirable, and it is to this issue which the present invention is directed.
An easily implemented error correction code is provided through the provision of a single symbol error correction and double symbol error detection code generated according to a novel, modular H-matrix. The H-matrix of the present invention utilizes a modular design with multiple iterations of a plurality of subsets and is thus easily implemented. In particular, one example of this H-matrix includes a plurality of rows and columns wherein each of at least one row of the H-matrix comprises, in part, multiple iterations of one subset of the plurality of subsets. The remainder of the rows, in turn, comprises, in part, a cyclic permutation of all of the remaining subsets of the plurality of subsets. By using this modular approach, the H-matrix of the present invention provides exceptional error protection and yet remains easily implemented.
In one example, a method of correcting errors in a data word is disclosed. The method includes generating an error correction code according to an H-matrix comprising a plurality of subsets arranged in a plurality of rows and columns, wherein each of at least one row of the plurality of rows comprises, in part, multiple iterations of one subset of the plurality of subsets, and a remainder of the plurality of rows comprises, in part, a cyclic permutation of all remaining subsets of the plurality of subsets; and detecting errors in the data word according to the error correction code.
In another example, a system of correcting errors in a data word includes, means for generating an error correction code according to an H-matrix comprising a plurality of subsets arranged in a plurality of rows and columns, wherein each of at least one of the plurality of rows comprises, in part, multiple iterations of one subset of the plurality of subsets, and a remainder of the plurality of rows comprises, in part, a cyclic permutation of all remaining subsets of the plurality of subsets; and means for detecting errors in the data word according to the error correction code.
In yet another example, an article of manufacture including at least one computer usable medium having computer readable program code means embodied therein for causing the correcting of errors in a data word is provided. The computer readable program code means includes computer readable program code means for causing a computer to generate an error correction code according to an H-matrix comprising a plurality of subsets arranged in a plurality of rows and columns, wherein each of at least one of the plurality of rows comprises, in part, multiple iterations of one subset of the plurality of subsets, and a remainder of the plurality of rows comprises, in part, a cyclic permutation of all remaining subsets of the plurality of subsets; and computer readable program code means for causing a computer to effect detecting errors in the data word according to the error correction code.
In this manner, the cyclic permutation structure of the H-matrix enables a common logic circuitry to generate check bits. Specifically, since a subset of a row is a permutation of the subset of another row, XOR trees for the generation of certain check bits are the same. Only the data inputs to the XOR trees are different.
Additional features and advantages are realized through the techniques of the present invention. Other embodiments and aspects of the invention are described in detail herein and are considered a part of the claimed invention.